题意

将题意转化一下

有 $m = \sum\limits_{i = 1}^n w_i$ 个数，前 $n$ 个中第 $i$ 个为 $w_i − 1$ ，剩下的 $m − n$ 个数都是 $− 1$

求对这 $m$ 个数 $m!$ 种重排的方案中，有多少种满足重排后的序列任意前缀和不为负

题解

卡特兰数的另一种组合意义

首先有一个引理

  • 给定 $n$ 个 $1$ 和 $n$ 个 $- 1$，它们组成一个长度为 $2n$ 的序列 $a$，则必定存在一个 $i$ 使得序列 $a_{i + 1…2n} + a_{1…i}$ 满足任意前缀都不小于零
  • 证明也很简单，找到一个使得前缀和最小的位置 $i$，设 $s_{i,j}$ 表示 $a$ 上 $a_i$ 到 $a_j$ 的和，那么显然 $s_{i + 1, 2n} \ge 0$，对 $\forall k \in [1, i]$，$s_{i + 1, 2n} + s_{1, k} \ge 0$

那么接下来求解 $n$ 个 $1$ 和 $n$ 个 $- 1$ 组成的合法序列（即任意前缀和不小于零）的方案数，也就是卡特兰数

$1$ 的编号为 $1 \sim n$，$- 1$ 的编号为 $n + 1 \sim 2n$

现在先假定所有 $1$ 和 $- 1$ 都是有标号的，那么最后乘上一个 $\frac1{n!n!}$ 就好了

由于直接看 $2n$ 的环可以断的地方较多无法处理，故考虑在后面接上一个编号为 $2n + 1$ 的 $- 1$，那么现在问题就变成给定一个 $2n + 1$ 长度的环，断开其中一处 $- 1$，得到的序列前 $2n$ 项任意前缀和非负，前 $2n + 1$ 项前缀和为 $- 1$

那么和上面同样取一个使前缀和最小的位置 $i$（若有多个则取最小的那一个），可以证明 $i$ 使唯一的

就那取第二个为例，设取第二个使前缀和最小的位置为 $j$，那么有 $s_{j + 1, 2n + 1} + s_{1, j} = - 1$，即 $s_{j + 1, 2n + 1} + s_{1, i} = - 1$，这样子就已经不满足条件了

证明了唯一性，也就是说断开方式是唯一的

由于此时 $- 1$ 使有标号的，总共有 $n + 1$ 个 $- 1$，也就是说所有 $2n + 1$ 个元素组成的环中平均每 $n + 1$ 个环就存在一个满足条件的，那么就可以得到卡特兰数的通项
$$
Cat_n = \frac{\frac{(2n + 1)!}{2n + 1}}{(n + 1)(n!)^2} = \frac{\dbinom{2n}{n}}{n + 1}
$$

回到题目

同样的，这 $m$ 个数组成的序列同样也满足存在一个位置 $i$ 使得 $s_{i + 1, m} + s_{1, i}$ 不小于零

故也在该序列后面加入一个编号为 $m + 1$ 的 $- 1$，连成环后断环方式唯一

那么答案即为 $\frac{m!}{m - n + 1}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 998244353

using namespace std;

typedef long long LL;

const int MAXM = 4e06 + 10;

LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

int n, m = 0;

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	n = getnum ();
	for (int i = 1; i <= n; i ++) m += getnum ();
	LL fact = 1;
	for (int i = 2; i <= m; i ++) fact = fact * i % MOD;
	cout << fact * power (m - n + 1, MOD - 2) % MOD << endl;

	return 0;
}